﻿// 873. 欧拉函数.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//


/*
https://www.acwing.com/problem/content/875/

给定 n 个正整数 ai，请你求出每个数的欧拉函数。

欧拉函数的定义
1∼N 中与 N 互质的数的个数被称为欧拉函数，记为 ϕ(N)。
若在算数基本定理中，N=pa11pa22…pamm，则：
ϕ(N) = N×p1−1p1×p2−1p2×…×pm−1pm
输入格式
第一行包含整数 n。

接下来 n 行，每行包含一个正整数 ai。

输出格式
输出共 n 行，每行输出一个正整数 ai 的欧拉函数。

数据范围
1≤n≤100,
1≤ai≤2×109
输入样例：
3
3
6
8
输出样例：
2
2
4
*/

#include <iostream>
#include <vector>

using namespace std;

int T;

void solve() {
	int n; cin >> n;
	if (n == 1) {
		cout << 1 << endl;
		return;
	}
	vector<int> prime;
	int cn = n;
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0) {
			prime.push_back(i);
			while (n % i == 0) {
				n /= i;
			}
		}
	}
	if (n != 1) {
		prime.push_back(n);
	}

	long long ans = cn;
	for (int i = 0; i < prime.size(); i++) {
		ans *= (prime[i] - 1);
		ans /= prime[i];
	}

	cout << ans << endl;

}


int main()
{
	cin >> T;
	while (T--) {
		solve();
	}

	return 0;
}
 